|
In computability theory, computational complexity theory and proof theory, a fast-growing hierarchy (also called an extended Grzegorczyk hierarchy) is an ordinal-indexed family of rapidly increasing functions ''f''α: N → N (where N is the set of natural numbers , and α ranges up to some large countable ordinal). A primary example is the Wainer hierarchy, or Löb–Wainer hierarchy, which is an extension to all α < ε0. Such hierarchies provide a natural way to classify computable functions according to rate-of-growth and computational complexity. ==Definition== Let μ be a large countable ordinal such that a fundamental sequence (a strictly increasing sequence of ordinals whose supremum is a limit ordinal) is assigned to every limit ordinal less than μ. A fast-growing hierarchy of functions ''f''α: N → N, for α < μ, is then defined as follows: * * * if α is a limit ordinal. Here ''f''α''n''(''n'') = ''f''α(''f''α(...(''f''α(''n''))...)) denotes the ''n''th iterate of ''f''α applied to ''n'', and α() denotes the ''n''th element of the fundamental sequence assigned to the limit ordinal α. (An alternative definition takes the number of iterations to be ''n''+1, rather than ''n'', in the second line above.) The initial part of this hierarchy, comprising the functions ''f''α with ''finite'' index (i.e., α < ω), is often called the Grzegorczyk hierarchy because of its close relationship to the Grzegorczyk hierarchy; note, however, that the former is here an indexed family of functions ''f''''n'', whereas the latter is an indexed family of ''sets'' of functions . (See Points of Interest below.) Generalizing the above definition even further, a fast iteration hierarchy is obtained by taking ''f''0 to be any increasing function g: N → N. For limit ordinals not greater than ε0, there is a straightforward natural definition of the fundamental sequences (see the Wainer hierarchy below), but beyond ε0 the definition is much more complicated. However, this is possible well beyond the Feferman–Schütte ordinal, Γ0, up to at least the Bachmann–Howard ordinal. Using Buchholz psi functions one can extend this definition easily to the ordinal of transfinitely iterated -comprehension (see Analytical hierarchy). A fully specified extension beyond the recursive ordinals is thought to be unlikely; e.g., Prӧmel ''et al.'' ()(p. 348) note that in such an attempt "there would even arise problems in ordinal notation". 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Fast-growing hierarchy」の詳細全文を読む スポンサード リンク
|